1. Field of the Invention
The present invention relates to computing, and more particularly, to a method, system, and apparatus for uniformly performing comparison operations on operands represented by more than one machine word. More specifically, the invention describes a new computer instruction that is used for performing long word comparison operations.
2. Description of Prior Art
Many popular CPU""s, such as the Intel IA32 family, the SPARC(trademark) processor from Sun Microsystems, Inc., the Power PC from IBM, and the Alpha processor from Digital Equipment Corporation, each have their own instruction set. When a programmer wishes to write a program to be executed by a particular CPU, the programmer composes the program from the corresponding instruction set. To run the program, the instructions are converted into machine instructions that are then executed by the CPU in program order.
Integer values are stored as words in the registers of the CPU whose size is defined by the particular CPU architecture. For example, in a 32-bit machine architecture, the word size is 32 bits. The registers in such a machine are therefore 32 bits wide.
The execution of an ADD or SUB instruction at the machine level is relatively straightforward. The corresponding bit positions of the two registers defined by the instruction are added or subtracted bit by bit from the least significant bit (LSB) to the most significant bit (MSB). Instruction sets also include a type of instruction generally called a conditional branch. With these types of instructions, execution typically continues at a new address which is specified with the conditional branch if the condition is met. If the condition is not met, execution usually continues with the next instruction in program order. A conditional branch tests if a particular condition occurred by analyzing certain flags. Typically, most CPUs store these certain flags in what is commonly referred to as the condition code register (CC register). CC registers usually hold a multitude of different flags, including but not exclusive, the sign flag S, the overflow/underflow flag V, the carry/borrow flag C, and the zero flag Z. Different conditional branches test for different conditions by checking for different flags to be set/cleared in the condition code register. For example, a conditional branch testing for the xe2x80x9cis zeroxe2x80x9d condition will test if the Z flag is set in the CC register at the time of the execution of the conditional branch. If the Z flag is set in the CC register, the conditional branch will continue at the new address, otherwise it will continue with the next instruction in program order.
The flags in condition code registers can be set via a multitude of ways. However, most CPUs automatically set the flags in the CC register according to the result of the previous instruction. For example, most CPUs have an ADD or SUB instruction that adds or subtracts the integer values stored in two registers, and then stores the result in one of the two or a third register. Usually, the ADD or SUB instruction will also update the flags in the CC register such that the status of the flags reflect the outcome of the result. For example, if the result after ADD or SUB is zero, the Z flag will be set in the CC register. Similarly, whenever a carry or borrow occurs, a carry flag C is set so that the hardware performing the addition or subtraction can take the carry or borrow condition into account for the next MSBs. One problem with addition or subtraction is that the sum or difference of the two integer operands may be too large or small to be represented in a 32-bit wide register. This event is called overflow with addition and underflow with subtraction. When an overflow/underflow condition occurs, an underflow/overflow flag V is set to indicate that the sum or difference of the two operands is too large or small to be represented in the register.
Usually, an ADD or SUB instruction (and many other instructions, for that matter) followed by a conditional branch instruction can be used together to control the execution of the program depending on the relation between two integer values. For example, if a conditional branch should occur depending on whether two integer values X1 and X2 are the same, the necessary instruction sequence would look as follows for many CPUs: First, the values of X1 and X2 are moved into corresponding registers R1 and R2. Then, a SUB instruction is used to subtract R2 from R1, and store the result in either R1, R2 or another register R3. The SUB instruction will also set the CC register""s flags depending on the result of the subtraction. If both X1 and X2 are the same, the result will be zero, otherwise it will not be zero. The Z flag in the CC register will be set automatically by the SUB instruction if the result is zero, otherwise it will be cleared. Thus, if and only if the Z flag is set in the CC register, X1 and X2 are the same. Therefore, a conditional branch testing the Z flag can be used to change the flow of a program depending on whether the two operands X1 and X2 are the same or not.
Because comparison of two integer values is a very important operation, most CPUs provide a special compare instruction CMP for that purpose. Such a CMP instruction usually behaves exactly like a SUB instruction, except that it does not store the result of the subtraction in one of the two or a third register. But like the SUB instruction, a CMP instruction updates the flags in the CC register. Thus, the CMP instruction is specially made to just subtract two integer values and update the CC accordingly, but discards the actual result. The advantage of the CMP instruction is that no register is changed to hold the result of the subtraction operation. Thus, the CMP instruction simply updates the flags in the CC register depending on the relation between the two integer values. A CMP instruction is usually followed by a conditional branch which tests the flags for a particular condition, depending on the relation that needs to be tested. In this way, conditional branches testing the CC flags can be used to change the flow of a program depending on the result of the comparison operation of the two operands.
It should be noted that the CMP instruction is helpful but not necessary, and that it can always be replaced with a SUB instruction if an extra unused register is available to store the result. For that reason and to not unnecessarily obscure the scope of the present invention, in the following we will not use CMP, but SUB instead. Table 1 below provides a listing of the relationship between certain relations for unsigned and two""s complement (i.e., signed) integer arithmetic and their corresponding flag settings. It suffices to say that most instruction sets provide conditional branch instructions testing the CC flags for conditions corresponding to the following relations: equal (=), not equal (!=), less than ( less than ), less than or equal ( less than =), greater than ( greater than ), or greater than or equal ( greater than =). It should also be noted that the conditions to be tested for these relations are different for signed (two""s complement) and unsigned integer arithmetic.
In this way, a conditional branch testing the CC flags can be used to change the control flow of a program depending upon the result of the comparison operation of the two operands. However, many programming languages, such as JAVA, Smalltalk, and C++, and the like, support arithmetic operations and comparisons of integer values more than one machine word wide. For example, a long integer in the JAVA programming language is 64-bits wide and therefore requires two words in a 32-bit machine (such as would be required in an Intel X86 architecture) to be represented. In other languages like Smalltalk, integer values can be arbitrarily long and thus may require multiple words to be represented.
As described above, comparing two 1-word integers essentially requires the subtraction of the two 1-word integers with a SUB instruction. The SUB instruction in turn will set the flags in the CC register accordingly and, if desired, a conditional branch testing the CC register flags can be used to change the program flow depending on the outcome of the comparison. Consequently, comparing two n-word integers (where n is greater than or equal to 1) should be done in the same way as is 1-word integers, by subtracting the two n-word integers and testing the CC register flags afterwards. For example, a 64 bit word D1 can be stored in two 32 bit registers (R1 and R2) in a 32 bit machine as shown in FIG. 1. Using the arrangement shown in FIG. 1, the register R2 stores the least significant 32 bits of the 64 bit data word D1 as a least significant word (LSW) D1L while the register R1 is used to store the most significant 32 bits as a most significant word (MSW) D1H. Similarly, a 64 bit word D2 can be stored in two 32 bit registers (R3 and R4) where the register R3 stores the 32 bit LSW of the 64 bit data word D2 (i.e; D2L) and the register R4 is used to store the 32 bit MSW of the 64 bit data word D2 (i.e; D2H).
As described above, the CC flags S, Z, V, and C are the flags tested by conditional branches for the six primitive compare operations ( less than ,  greater than , =, xe2x89xa0, xe2x89xa6, xe2x89xa7). The S flag depends only on the sign of the result (which is the most significant bit in a 2""s complement representation), while the V flag indicates internal carry for the second most significant bit to the most significant bit of the result, and the C flag indicates carry to or borrow from the next word. Since the S, V, and C flags depend only on the operation applied and result obtained for the most significant word of an n-word integer, the S, V, and C flags are correctly set for both 1 and n-word subtractions using either a conventional SBB (subtraction with borrow) or a SUB operation. In order, therefore, to compare the n-word data words D1 and D2, the LSWs of each data word (i.e., D1L and D2L) and the MSWs (i.e., D1H and D2H) of each data word are subtracted from each other using what is referred to as a subtraction (SUB) without borrow instruction and a subtraction with borrow (SBB) instruction. It should be noted that the first subtraction uses the SUB operation since the first subtraction needs to set the Z flag based upon the result of the subtraction and ignore the C flag. Also, it should be noted that the SBB instruction is working like the SUB instruction, but that it additionally takes into account the state of the C flag for the subtraction (in which case the C flag indicates xe2x80x9cborrowxe2x80x9d).
Unfortunately, however, the Z flag depends on all bits of an integer and if the integer is represented by more than one data word, information about the bits of all words must be comprehended in the computation. Since the subtraction of two n-word integers requires n subtractions starting with the least significant word, and since the SBB operation sets the Z flag only according to the result of the most recent SBB operation, the conditional operations that require testing of the Z flag (i.e.,  greater than , xe2x89xa6, xe2x89xa0, and =) will not work properly. For example, using the comparison of long data words D1 and D2, the result of the SBB operation on the MSWs of D1 and D2 will be the only result comprehended in the state of the Z flag regardless of the results of previous SBB operations for the lower order words.
Therefore, in order for multi-word comparison to be a uniform extension of the single-word comparison, what is required is a subtraction operation that maintains information about all the bits in comparing two n-word integers.
The invention relates to a method, apparatus and system for comparing a first multi-word operand with a second multi-word operand. In one embodiment, the first multi-word operand is formed of n words (where n is greater than or equal to 1) hierarchically arranged from a first operand lowest order word (LSW) to a first operand highest order word (MSW) while the second operand is formed of n words hierarchically arranged from a second operand lowest order word (LSW) to a second operand highest order word (MSW).
As a method, using a subtraction without borrow operation, the first operand lowest order word is subtracted from a second operand lowest order word. If the result of the subtracting is not zero, then a zero (Z) flag is cleared such that a Z flag status is not set. If, however, the result of the subtracting is zero, then the Z flag is set as usual. Next, a first operand next higher order word is subtracted from a second operand next higher order word using a subtraction with borrow and a sticky not Z flag (SBBZ) instruction and, based upon the subtracting, the Z flag is updated accordingly until the first operand highest order word is subtracted from the second operand highest order word. The comparing of the first operand and the second operand is then based upon the Z flag status, if needed, after the subtraction of the first operand highest order word is subtracted from the second operand highest order word. In this way, the method can be used for comparing the multi-word width operands of any conditional branch instruction which defines one of the following relations: equal (=); not equal (xe2x89xa0); less than ( less than ); less than or equal (xe2x89xa6); greater than ( greater than ); or greater than or equal (xe2x89xa7).
In another embodiment, a CPU configured to execute a machine instruction requiring a comparison of two multi-word operands for execution is described. The CPU includes a zero (Z) flag, subtraction circuitry configured to perform a subtraction operation on each of the words of the two multi-word operands respectively, and reset circuitry configured to reset the Z flag such that a Z flag status is not set if any of the subtraction operations on the two multi-word operands is not zero.